package com.mlh.dp.old;

// 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
// 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
// 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
// 注意：不允许旋转信封。

// 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
// 输出：3
// 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

import java.util.*;
//读题思考： 1)信封不能等大 长和宽都不能等大  2）一个信封内在同一空间 只能有同一个信封  3)联想最长递增子序列
//子序列是不能调换顺序的  而信封是可以的
public class MaxEnvelopes {

    public static void main(String[] args) {
        int [][]envelopes={{46,89},{50,53},{52,68},{72,45},{77,81}};
        method2(envelopes);
    }

    //二维动态规划解 会超出时间限制  理论上思路是对的
    public  static int method1(int[][]envelopes){
        Arrays.sort(envelopes,(a, b) -> a[0] - b[0]);
        System.out.println(Arrays.deepToString(envelopes));
        int[]dp=new int[envelopes.length];
        dp[0]=1;
        int res=0;
        for(int i=1;i<dp.length;i++){
            dp[i]=1;
            for(int j=i-1;j>=0;j--){
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res=Math.max(dp[i],res);
        }
        System.out.println(Arrays.toString(dp));
        return res;
    }

    public static int method2(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        }
        //解题的关键是这个排序  通过排序过后他将这个问题转变成了一维的最长递增子序列问题
        //这个排序先根据w（或者h也行）进行大小排序  如果此时就在h上做一个递增子序列  会出现以下情况
        //排完序的结果为 [(w,h)]=[(1,1),(1,2),(1,3),(1,4)]，
        //由于这些信封的w值都相同，不存在一个信封可以装下另一个信封，
        //那么我们只能在其中选择1个信封。
        //然而如果我们完全忽略w维度，剩下的h维度为 [1,2,3,4]，
        //这是一个严格递增的序列，那么我们就可以选择所有的4个信封了，这就产生了错误。
        //因此，我们必须要保证对于每一种w值，我们最多只能选择1个信封。
        // 我们可以将h值作为排序的第二关键字进行降序排序，这样一来，对于每一种w值，
        // 其对应的信封在排序后的数组中是按照h值递减的顺序出现的，那么这些h值不可能组成长度超过1的严格递增的序列，这就从根本上杜绝了错误的出现。
        // 因此我们就可以得到解决本题需要的方法：
        // 首先我们将所有的信封按照w值第一关键字升序、h值第二关键字降序进行排序；
        // 随后我们就可以忽略w维度，求出h维度的最长严格递增子序列，其长度即为答案。

        int n = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) {
                    return e1[0] - e2[0];
                } else {
                    return e2[1] - e1[1];
                }
            }
        });

        //这边接下来的解题步骤就是最长递增子序列 没有任何的差别
        int[] d = new int[n];
        int len = 0;
        d[0] = envelopes[0][1];
        for (int i = 1; i < d.length; i++) {
            if (d[len] < envelopes[i][1]) {
                d[++len] = envelopes[i][1];
            } else {
                //这里就是二分查找
                int l = 0;
                int r = len;
                int pos =-1;
                while (l <= r) {
                    int mid = l + r >> 1;
                    if (d[mid] < envelopes[i][1]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = envelopes[i][1];
            }
        }
        return len + 1;
    }
}